package tree.leetcode_144_medium;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class newcoder {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        int[][] ints = new newcoder().threeOrders(root);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(Arrays.toString(ints[i]));
        }
    }

    private int preIndex = 0, inIndex = 0, postIndex = 0;

    public int[][] threeOrders(TreeNode root) {
        // write code here
        int len = count(root);
        int[][] orders = new int[3][len];
        dfs(root, orders);
        return orders;
    }

    public void dfs(TreeNode root, int[][] orders) {
        if (root == null) {
            return;
        }
        //先序
        Deque<TreeNode> preStack = new LinkedList<>();
        preStack.addFirst(root);
        while (!preStack.isEmpty()) {
            TreeNode cur = preStack.removeFirst();
            orders[0][preIndex++] = cur.val;
            if (cur.right != null) {
                preStack.addFirst(cur.right);
            }
            if (cur.left != null) {
                preStack.addFirst(cur.left);
            }
        }
        //中序
        Deque<TreeNode> inStack = new LinkedList<>();
        TreeNode cur = root;
        while (!inStack.isEmpty() || cur != null) {
            if (cur != null) {
                inStack.addFirst(cur);
                cur = cur.left;
            } else {
                cur = inStack.removeFirst();
                orders[1][inIndex++] = cur.val;
                cur = cur.right;
            }
        }
        //后序
        Deque<TreeNode> postStack1 = new LinkedList<>();
        Deque<TreeNode> postStack2 = new LinkedList<>();
        postStack1.addFirst(root);
        while (!postStack1.isEmpty()) {
            TreeNode temp = postStack1.removeFirst();
            postStack2.addFirst(temp);
            //先左后右，出栈先右后左，在放入栈先右后左，出栈，先左后右
            if (temp.left != null) {
                postStack1.addFirst(temp.left);
            }
            if (temp.right != null) {
                postStack1.addFirst(temp.right);
            }
        }
        while (!postStack2.isEmpty()) {
            TreeNode temp = postStack2.removeFirst();
            orders[2][postIndex++] = temp.val;
        }
    }

    public int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + count(root.left) + count(root.right);
    }
}
